import java.util.LinkedList;
import java.util.Queue;

//二叉树序列化和反序列化
public class TreeSerialization {
}
class TreeSerializationCodec {
    Queue<TreeNode> queue = new LinkedList();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        String str = "";
        if(root==null)return "#!";
        str+=root.val+"!";
        queue.add(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            if(root.left==null)
                str+="#!";
            else{
                str+=root.left.val+"!";
                queue.add(root.left);
            }
            if(root.right==null)
                str+="#!";
            else{
                str+=root.right.val+"!";
                queue.add(root.right);
            }
        }
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] str = data.split("!");
        int index = 0;
        if(str[0].equals("#"))return null;
        TreeNode node = new TreeNode(Integer.valueOf(str[index++]));
        TreeNode head = node;
        queue.add(node);
        while(!queue.isEmpty()){
            node = queue.poll();
            if(!str[index].equals("#")){
                node.left = new TreeNode(Integer.valueOf(str[index]));
                queue.add(node.left);
            }
            index++;
            if(!str[index].equals("#")){
                node.right = new TreeNode(Integer.valueOf(str[index]));
                queue.add(node.right);
            }
            index++;
        }
        return head;
    }
}